package top.ivansong92.example.leetcode.learning.common.algorithms.dynamic;


import org.junit.Test;
import top.ivansong92.example.leetcode.learning.data.struct.tree.TestExample;

import java.util.*;

public class TestExample2 {
    @Test
    public void testintegerBreak() {
        rob(new int[]{1, 3, 1});
    }


    /**
     * 198. 打家劫舍
     * https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/23/dynamic-programming/57/
     *
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int len = nums.length;
        if (len == 1) {
            return nums[0];
        }

        if (len == 2) {
            return Math.max(nums[0], nums[1]);
        }

        Integer[] temp = new Integer[len];

        return doRob(nums, 0, len, temp);
    }

    /**
     * 213. 打家劫舍 II
     *
     * @param nums
     * @return
     */
    public int rob2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int len = nums.length;
        if (len == 1) {
            return nums[0];
        }

        if (len == 2) {
            return Math.max(nums[0], nums[1]);
        }
        Integer[] temp = new Integer[len - 1];
        int a1 = doRob(Arrays.copyOfRange(nums, 0, len - 1), 0, len - 1, temp);
        temp = new Integer[len - 1];

        int a2 = doRob(Arrays.copyOfRange(nums, 1, len), 0, len - 1, temp);
        return Math.max(a1, a2);
    }

    @Test
    public void testrob2V2() {
        rob2V2(new int[]{200, 3, 140, 20, 10});
    }

    public int rob2V2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int len = nums.length;
        if (len == 1) {
            return nums[0];
        }

        if (len == 2) {
            return Math.max(nums[0], nums[1]);
        }

        int[] includeFirst = new int[len - 1];
        includeFirst[0] = nums[0];
        includeFirst[1] = Math.max(nums[0], nums[1]);

        int[] excludeFirst = new int[len - 1];
        excludeFirst[0] = nums[1];
        excludeFirst[1] = Math.max(nums[1], nums[2]);

        for (int i = 2; i < len - 1; i++) {
            includeFirst[i] = Math.max(includeFirst[i - 1], includeFirst[i - 2] + nums[i]);
            excludeFirst[i] = Math.max(excludeFirst[i - 1], excludeFirst[i - 2] + nums[i + 1]);
        }

        return Math.max(includeFirst[len - 2], excludeFirst[len - 2]);
    }

    private int doRob(int[] nums, int start, int max, Integer[] tmp) {
        if (start >= max) {
            return 0;
        }

        if (tmp[start] != null) {
            return tmp[start];
        }
        int res = 0;

        for (int i = start; i < max; i++) {
            res = Math.max(res, nums[i] + doRob(nums, i + 2, max, tmp));
        }
        tmp[start] = res;
        return res;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    /**
     * 337. 打家劫舍 III
     *
     * @param root
     * @return
     */
    public int rob(TreeNode root) {
        if (root == null) {
            return 0;
        }

        if (root.left == null && root.right == null) {
            return root.val;
        }

        return doRob(root, new HashMap<>());
    }

    private int doRob(TreeNode node, Map<TreeNode, Integer> levelMap) {
        if (node == null) {
            return 0;
        }
        Integer val = levelMap.get(node);
        if (val != null) {
            return val;
        }

        int a1 = node.val;
        //尝试偷该节点
        if (node.left != null) {
            a1 += doRob(node.left.left, levelMap) + doRob(node.left.right, levelMap);
        }
        if (node.right != null) {
            a1 += doRob(node.right.left, levelMap) + doRob(node.right.right, levelMap);
        }

        int a2 = doRob(node.left, levelMap) + doRob(node.right, levelMap);

        int res = Math.max(a1, a2);

        levelMap.put(node, res);
        return res;
    }

    public int robV2(TreeNode root) {
        if (root == null) {
            return 0;
        }

        if (root.left == null && root.right == null) {
            return root.val;
        }

        return Math.max(doRob(root, true), doRob(root, false));
    }

    private int doRob(TreeNode node, boolean include) {
        if (node == null) {
            return 0;
        }

        if (include) {
            return node.val + doRob(node.left, false) + doRob(node.right, false);
        } else {
            int a1 = doRob(node.left, false);
            int a2 = doRob(node.left, true);

            int b1 = doRob(node.right, false);
            int b2 = doRob(node.right, true);
            return Math.max(Math.max(a1 + b1, a1 + b2), Math.max(a2 + b1, a2 + b2));
        }
    }

    public int robV3(TreeNode root) {
        if (root == null) {
            return 0;
        }

        if (root.left == null && root.right == null) {
            return root.val;
        }

        int[] array = doRobV3(root);

        return Math.max(array[0], array[1]);
    }

    private int[] doRobV3(TreeNode node) {
        if (node == null) {
            return new int[2];
        }
        int[] res = new int[2];
        int[] left = doRobV3(node.left);

        int[] right = doRobV3(node.right);

        res[0] = Math.max(right[0], right[1]) + Math.max(left[0], left[1]);
        res[1] = left[0] + right[0] + node.val;
        return res;
    }

    public int robV4(TreeNode root) {
        if (root == null) {
            return 0;
        }

        if (root.left == null && root.right == null) {
            return root.val;
        }

        return doRobV4(root)[2];
    }

    private int[] doRobV4(TreeNode node) {
        if (node == null) {
            return new int[3];
        }
        int[] res = new int[3];
        int[] left = doRobV4(node.left);

        int[] right = doRobV4(node.right);

        res[0] = left[2] + right[2];
        res[1] = left[0] + right[0] + node.val;
        res[2] = Math.max(res[0], res[1]);
        return res;
    }


    //0-1背包问题
    public int getMaxKnapsack(int[] weight, int[] value, int capacity) {
        if (weight == null || value == null) {
            return 0;
        }

        int len = weight.length;
        if (len == 1) {
            return weight[0] > capacity ? 0 : value[0];
        }

        List<Bag> bagList = new ArrayList<>();
        for(int i = 0; i < len; i ++) {
            if (weight[i] > capacity) {
                continue;
            }
            Bag bag = new Bag();
            bag.weight = weight[i];
            bag.value = value[i];
            bagList.add(bag);
        }

        bagList.sort(Comparator.comparing(Bag::getWeight));

        return doGetK(bagList, capacity, bagList.size() - 1, new Integer[bagList.size()][capacity + 1]);
    }

    private int doGetK(List<Bag> bagList, int capacity, int index, Integer[][] array) {
        if (index < 0 || capacity <= 0) {
            return 0;
        }


        if (array[index][capacity] != null) {
            return array[index][capacity];
        }

        int res = doGetK(bagList, capacity, index - 1, array);
        Bag bag = bagList.get(index);
        if (bag.weight <= capacity) {
            res = Math.max(res, bag.value + doGetK(bagList, capacity - bag.weight, index - 1, array));
        }

        array[index][capacity] = res;
        return res;
    }

    public int getMaxKnapsackV2(int[] weight, int[] value, int capacity) {
        if (weight == null || value == null) {
            return 0;
        }

        int len = weight.length;
        if (len == 1) {
            return weight[0] > capacity ? 0 : value[0];
        }
        return doGetK(weight, value, capacity, len - 1, new Integer[len][capacity + 1]);
    }

    private int doGetK(int[] weight, int[] value, int capacity, int index, Integer[][] array) {
        if (index < 0 || capacity <= 0) {
            return 0;
        }


        if (array[index][capacity] != null) {
            return array[index][capacity];
        }

        int res = doGetK(weight, value, capacity, index - 1, array);
        if (weight[index] <= capacity) {
            res = Math.max(res, value[index] + doGetK(weight, value, capacity - weight[index], index - 1, array));
        }

        array[index][capacity] = res;
        return res;
    }

    private static class Bag {
        int weight;
        int value;

        public int getWeight() {
            return this.weight;
        }
    }

    /**
     * 动态规划-背包问题
     * @param weight
     * @param value
     * @param capacity
     * @return
     */
    public int getMaxKnapsackV3(int[] weight, int[] value, int capacity) {
        if (weight == null || value == null || weight.length != value.length) {
            return 0;
        }

        int len = weight.length;
        if (len == 1) {
            return weight[0] > capacity ? 0 : value[0];
        }

        List<Bag> bagList = new ArrayList<>();
        for(int i = 0; i < len; i ++) {
            if (weight[i] > capacity) {
                continue;
            }
            Bag bag = new Bag();
            bag.weight = weight[i];
            bag.value = value[i];
            bagList.add(bag);
        }

        int n = bagList.size();
        bagList.sort(Comparator.comparing(Bag::getWeight));

        int[][] bagArray = new int[n][capacity + 1];
        Bag bag = bagList.get(0);
        for (int j = 0; j <= capacity; j ++) {
            bagArray[0][j] = bag.weight >= j ? bag.value : 0;
        }

        for (int i = 1; i < n; i++) {
            bag = bagList.get(i);
            for(int j = 0; j <= capacity; j ++) {
                bagArray[i][j] = bagArray[i - 1][j];
                if (bag.weight < j) {
                    continue;
                }
                bagArray[i][j] = Math.max(bagArray[i - 1][j], bagArray[i - 1][j - bag.weight] + bag.value);
            }
        }
        return bagArray[n - 1][capacity];
    }

    /**
     * 优化空间利用1
     * @param weight
     * @param value
     * @param capacity
     * @return
     */
    public int getMaxKnapsackV4(int[] weight, int[] value, int capacity) {
        if (weight == null || value == null || weight.length != value.length) {
            return 0;
        }

        int len = weight.length;
        if (len == 1) {
            return weight[0] > capacity ? 0 : value[0];
        }

        List<Bag> bagList = new ArrayList<>();
        for(int i = 0; i < len; i ++) {
            if (weight[i] > capacity) {
                continue;
            }
            Bag bag = new Bag();
            bag.weight = weight[i];
            bag.value = value[i];
            bagList.add(bag);
        }

        int n = bagList.size();
        bagList.sort(Comparator.comparing(Bag::getWeight));

        int[][] bagArray = new int[2][capacity + 1];
        Bag bag = bagList.get(0);
        for (int j = 0; j <= capacity; j ++) {
            bagArray[0][j] = bag.weight >= j ? bag.value : 0;
        }

        for (int i = 1; i < n; i++) {
            bag = bagList.get(i);
            int k = i % 2;
            int m = (i + 1) % 2;
            for(int j = 0; j <= capacity; j ++) {
                bagArray[k][j] = bagArray[m][j];
                if (bag.weight < j) {
                    continue;
                }
                bagArray[k][j] = Math.max(bagArray[m][j], bagArray[m][j - bag.weight] + bag.value);
            }
        }
        return bagArray[n % 2][capacity];
    }

    /**
     * 优化空间利用2
     * @param weight
     * @param value
     * @param capacity
     * @return
     */
    public int getMaxKnapsackV5(int[] weight, int[] value, int capacity) {
        if (weight == null || value == null || weight.length != value.length) {
            return 0;
        }

        int len = weight.length;
        if (len == 1) {
            return weight[0] > capacity ? 0 : value[0];
        }

        List<Bag> bagList = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            if (weight[i] > capacity) {
                continue;
            }
            Bag bag = new Bag();
            bag.weight = weight[i];
            bag.value = value[i];
            bagList.add(bag);
        }

        int n = bagList.size();
        bagList.sort(Comparator.comparing(Bag::getWeight));

        int[] bagArray = new int[capacity + 1];
        Bag bag = bagList.get(0);
        for (int j = 0; j <= capacity; j++) {
            bagArray[j] = bag.weight >= j ? bag.value : 0;
        }

        for (int i = 1; i < n; i++) {
            bag = bagList.get(i);
            for (int j = capacity; j >= 0; j--) {
                if (j < bag.weight) {
                    continue;
                }
                bagArray[j] = Math.max(bagArray[j], bagArray[j - bag.weight] + bag.value);
            }
        }
        return bagArray[capacity];
    }

    @Test
    public void testCanPartition() {
        System.out.println(canPartition(new int[]{200, 260, 180, 120}));
    }
    /**
     * 416. 分割等和子集
     * @param nums
     * @return
     */
    /**
     * 回溯-记忆化搜索
     * @param nums
     * @return
     */
    public boolean canPartition(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return false;
        }

        int sum = 0;
        for (int n : nums) {
            sum += n;
        }

        if (sum % 2 == 1) {
            return false;
        }

        int avg = sum / 2;

        return doTryPartition(nums, nums.length - 1, avg, new Boolean[nums.length - 1][avg + 1]);
    }

    private boolean doTryPartition(int[] nums, int index, int sum, Boolean[][] array) {
        if (sum == 0) {
            return true;
        }
        if (index < 0 || sum < 0) {
            return false;
        }
        Boolean e = array[index][sum];
        if (e != null) {
            return e;
        }
        e = doTryPartition(nums, index - 1, sum, array) || doTryPartition(nums, index - 1, sum - nums[index], array);
        array[index][sum] = e;
        return e;
    }


    public boolean canPartitionV2(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return false;
        }

        int sum = 0;
        for (int n : nums) {
            sum += n;
        }

        if (sum % 2 == 1) {
            return false;
        }

        int avg = sum / 2;
        int len = nums.length;
        boolean[] array = new boolean[avg + 1];
        for(int i = 0; i <= avg; i ++) {
            array[i] = i == nums[0];
        }
        for(int i = 1; i < len; i ++) {
            int n = nums[i];
            for(int j = avg; j >= n; j --) {
                array[j] = array[j] || array[j - n];
            }
        }
        return array[avg];
    }

    public static String booleanToString(boolean input) {
        return input ? "True" : "False";
    }
}